Comparing Java and Ada Monitors
queuing policies: a case study
Java
deadlock free implementation
1. How to run the Java deadlock free implementation
The main program is diner.adb
Once compiled (with GNAT for example), just run ./diner
-- JAVA implementation simulated with an Ada protected object
-- simulates Java concurrency semantics
-- the Java wait operation is here an entry call with a barrier
-- one Java synchronized method simulated by Get_LR and requeue Get_R
-- allocates left stick first if it is available and not booked and
then also right stick if available. If right is not available, it is
booked.
-- waits if one or both sticks have not been allocated
-- ******** reliable, deadlock free
2. A new solution for a
well known
paradigm, the dining philosophers
The dining philosophers, originally posed by Dijkstra
[Dijkstra 7I], is a paradigm for concurrent resource allocation. Five
philosophers spend their life alternately thinking and eating. To dine,
each philosopher sits around a circular table at a fixed place. In
front of each philosopher is a plate of food, and between each pair of
philosophers is a chopstick. In order to eat, a philosopher needs two
chopsticks, and they agree that each will use only the chopsticks
immediately to the left and to the right of his place. The problem is
to write a program simulating the philosopher’s behaviours and to
devise a protocol that avoids two unfortunate conclusions. In the first
one, all philosophers are hungry but none is able to acquire both
chopsticks since each holds one chopstick and refuses to give it up.
This is deadlock, a safety concern. In the second one, a hungry
philosopher will always lack one of the two chopsticks which are
alternately used by its neighbours. This is starvation, a liveness
consideration.
This paradigm has two well known approaches for obtaining a solution.
In the first one, the chopsticks are allocated one by one, and a
reliable solution is obtained by adding one of the usual constraints
for deadlock prevention: the chopsticks are allocated in fixed (e.g.,
increasing) order; a chopstick allocation is denied as soon as the
requested allocation would lead to an unsafe state (seated dinner, with
only 4 chairs). Ada implementation of this approach can be found [Burns
1995, Barkaoui 1997]. In the second one, the chopsticks are allocated
globally only, which is a safe solution; when a fair solution is
necessary, it is obtained by adding reservation constraints, care being
taken that these constraints do not reintroduce deadlock. Ada
implementation are given in [Brosgol 1996, Kaiser 1997]
Let us consider now another approach which does not seem to have been
much experimented except in [Kaiser 1997]. The chopsticks are allocated
as many as available and the allocation is completed as soon as the
missing chopsticks are released. Let us observe the behaviour of this
solution when implemented in Java and in Ada and from these
experiments, let us determine the conditions of its correctness.
3. Java reliable implementation
3.1. The Java class
A modified Java implementation leads to the following Chop
class
with get_LR and release methods.
This implementation is reliable.
public final class Chop {
private int N ;
private boolean available [ ] ;
private boolean booked [ ] ;
Chop (int N) {
this.N = N ;
this.available = new boolean[N] ;
for (int i =0 ; i < N ; i++) {
available[i] =
true ; // non allocated stick
booked[i] = false;
}
}
public synchronized void get_LR (int me) {
int score = 0 ; // useful when
simulating the Java solution in Ada
while (!available [me]
|| booked[me]) {
try { wait() ;
} catch (InterruptedException e) {}
}
available [me] = false ; score =
1; // left stick allocated
booked[(me + 1)% N] ==
true; // right stick booked
// don’t release mutual exclusion
lock and immediately requests second stick
while (!available [(me + 1)% N]) {
try { wait() ;
} catch (InterruptedException e) {}
}
available [(me + 1)% N] =
false ; score = 2; // both sticks allocated
booked[(me + 1)% N] ==
false; // no more reason for booking right stick
}
public synchronized void release (int me) {
available [me] = true ; available
[(me + 1)% N] = true ;
notifyAll ;
}
}
3.2. Ada simulation
of the
Java deadlock free implementation
Transcribing this Java implementation in
an Ada program with the eggshell semantics requires an entry
for each waiting condition.
The solution is in chop.adb
The solution is instrumented for measuring a concurrency
denials ratio.
4. The full paper : Comparing
Java and Ada Monitors
queuing policies: a case study